package cn.datastruct.EightTree;

import java.util.*;

import static cn.datastruct.five.HeapSort.heapSort;

/**
 * 思路：
 * 1.将数组进行降序排序，每一个数都是一个简单的二叉树
 * 2.取出权值最小的两个二叉树
 * 3.组成一个新的二叉树，新二叉树的root为两个节点的和
 * 4.在将数组进行排序
 * 5.重复1、2、3、4直到节点全被处理的时候
 */
public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {13, 8, 12, 14, 9, 6, 10};
        huffmanTree(arr);
    }

    public static void huffmanTree(int[] arr) {
        //创建一个node类型的数组列表
        List<Node> nodelist = new ArrayList<>();

        //保存数组长度
        int length = arr.length;

        for (int i = 0; i < length; i++) {
            nodelist.add(new Node(arr[i]));
        }
        Collections.sort(nodelist);
        //求出两个最小的值相加并重新排序
        while (nodelist.size() > 1) {
            Node leftNode = nodelist.get(0);
            Node rightNode = nodelist.get(1);
            //构建两个最小二叉树
            Node parent = new Node(leftNode.val + rightNode.val);
            parent.left = leftNode;
            parent.right = rightNode;

            //去除节点
            nodelist.remove(1);
            nodelist.remove(0);

            //添加parent节点
            nodelist.add(parent);

            //重新排序
            Collections.sort(nodelist);
        }
        System.out.println(nodelist);
    }
}

class Node implements Comparable<Node> {
    //成员变量
    int val;
    Node left;
    Node right;

    public Node(int val) {//构造节点
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.val - o.val;
    }
}
